﻿using System;
using System.Diagnostics;

namespace System.Collections.Generic
{
	public class FixedPool<T> where T : class
	{
		protected struct PoolComparer : IComparer<T>
		{
			public Comparison<T> Comp;

			public int Compare(T x, T y)
			{
				return Comp(x, y);
			}
		}

		public delegate T TAllocator(FixedPool<T> pool);
		public delegate int SearchComparison<T2>(T x, T2 y);
		protected T[] Cache;
		protected T[] Pool;

		public int Capacity
		{
			get
			{
				return Cache.Length;
			}
		}

		public int AllocCount
		{
			get;
			protected set;
		}

		public int FreeCount
		{
			get;
			protected set;
		}

		public int Count
		{
			get;
			protected set;
		}

		public FixedPool<T>.TAllocator Allocator { get; set; }

		public T this[int idx]
		{
			get
			{
				return Pool[idx];
			}
		}

		protected FixedPool()
		{
		}

		public FixedPool(int capacity)
		{
			if (capacity <= 0)
			{
				throw new InvalidOperationException(string.Format("ERROR: new FixedPool create failed. invalid param. capacity = {0}, reserveCount = 0", capacity));
			}

			Cache = new T[capacity];
			Pool = new T[capacity];
		}

		public FixedPool(int capacity, int reserveCount, FixedPool<T>.TAllocator allocator)
		{
			if (capacity <= 0 || reserveCount < 0)
			{
				throw new InvalidOperationException(string.Format("ERROR: new FixedPool create failed. invalid param. capacity = {0}, reserveCount = {1}", capacity, reserveCount));
			}

			if (capacity < reserveCount)
			{
				throw new InvalidOperationException(string.Format("ERROR: new FixedPool create failed. capacity < reserveCount. capacity = {0}, reserveCount = {1}", capacity, reserveCount));
			}

			Cache = new T[capacity];
			Pool = new T[capacity];
			Allocator = allocator;
			ReserveAdd(reserveCount);
		}

		public T Alloc()
		{
			if (Count >= Capacity)
			{
				throw new OverflowException(string.Format("ERROR: FixedPool.Add() failed. capacity = {0}, count = {1}", Capacity, Count));
			}

			if (FreeCount == 0)
			{
				ReserveAdd(1);
			}

			FreeCount--;
			T t = Cache[FreeCount];
			Pool[Count] = t;
			Count++;

			return t;
		}

		public T AllocAt(int idx)
		{
			if (idx < 0 || idx < Count)
			{
				throw new ArgumentOutOfRangeException(string.Format("ERROR: FixedPool.AddAt() failed. idx = {0}, count = {1}", idx, Count));
			}

			if (Count >= Capacity)
			{
				throw new OverflowException(string.Format("ERROR: FixedPool.AddAt() failed. capacity = {0}, count = {1}", Capacity, Count));
			}

			if (FreeCount == 0)
			{
				ReserveAdd(1);
			}

			FreeCount--;
			T t = Cache[FreeCount];

			for (int num = Count - 1; num != idx - 1; num--)
			{
				Pool[num + 1] = Pool[num];
			}

			Pool[idx] = t;
			Count++;

			return t;
		}

		public void ReserveAdd(int reserveCount)
		{
			if (AllocCount + reserveCount > Capacity)
			{
				throw new OverflowException(string.Format("ERROR: FixedPool.ReserveAdd() failed. capacity = {0}, alloc count = {1}, add count = {2}, alloc count + add count = {3}", 
					Capacity,
					AllocCount,
					reserveCount,
					AllocCount + reserveCount
				));
			}

			if (Allocator == null)
			{
				throw new InvalidOperationException("ERROR: FixedPool.ReserveAdd() failed. the allocator is null");
			}

			for (int i = 0; i < reserveCount; i++)
			{
				Cache[FreeCount + i] = Allocator(this);
			}

			FreeCount += reserveCount;
			AllocCount += reserveCount;
		}

		public void ReserveAddSafe(int reserveCount)
		{
			if (AllocCount + reserveCount > Capacity)
			{
				reserveCount = Capacity - AllocCount;
			}

			ReserveAdd(reserveCount);
		}

		public bool Remove(T item)
		{
			int idx = IndexOf(item);

			if (idx == -1)
			{
				return false;
			}

			RemoveAt(idx);
			return true;
		}

		public void RemoveAt(int idx)
		{
			if (idx < 0 || idx >= Count)
			{
				throw new ArgumentOutOfRangeException(string.Format("ERROR: FixedPool.RemoveAt() failed. idx = {0}, count = {1}", idx, Count));
			}

			Cache[FreeCount] = Pool[idx];
			FreeCount++;

			for (int i = idx + 1; i < Count; i++)
			{
				Pool[i - 1] = Pool[i];
			}

			Count--;
		}

		public void RemoveRange(int startIdx, int count)
		{
			if (count == 0)
			{
				return;
			}

			int tail = startIdx + count;
			if (startIdx >= Count || tail > Count)
			{
				throw new ArgumentOutOfRangeException(string.Format("ERROR: FixedPool.RemoveRange() failed. start idx = {0}, end idx = {1}, count = {2}", startIdx, num, Count));
			}

			for (int i = startIdx; i < count; i++)
			{
				Cache[FreeCount + i] = Pool[i];
			}
			if (tail < Count)
			{
				for (int j = tail; j < Count; j++)
				{
					Pool[j - count] = Pool[j];
				}
			}

			FreeCount += count;
			Count -= count;
		}

		public void Clear()
		{
			for (int i = 0; i < Count; i++)
			{
				Cache[FreeCount + i] = Pool[i];
			}

			FreeCount += Count;
			Count = 0;
		}

		public void Purge()
		{
			Clear();

			for (int i = 0; i < FreeCount; i++)
			{
				Cache[i] = (T)((object)null);
			}

			FreeCount = 0;
			AllocCount = 0;
		}

		public int BinarySearch<T2>(T2 item, FixedPool<T>.SearchComparison<T2> comparison)
		{
			return BinarySearch<T2>(0, Count, item, comparison);
		}

		public int BinarySearch<T2>(int startIdx, int count, T2 item, FixedPool<T>.SearchComparison<T2> comparison)
		{
			if (count == 0)
			{
				return -1;
			}

			int tail = startIdx + count;
			int mid = startIdx + count / 2;
			int comp = comparison(Pool[mid], item);

			if (comp > 0)
			{
				return BinarySearch<T2>(mid + 1, tail - mid - 1, item, comparison);
			}

			if (comp < 0)
			{
				return BinarySearch<T2>(startIdx, mid - startIdx, item, comparison);
			}

			return mid;
		}

		public bool Contains(T item)
		{
			return IndexOf(item) != -1;
		}

		public void ForEach(Action<T> action)
		{
			for (int i = 0; i < Count; i++)
			{
				action(Pool[i]);
			}
		}

		public int IndexOf(T item)
		{
			return IndexOf(item, 0, Count);
		}

		public int IndexOf(T item, int startIdx)
		{
			if (startIdx > Count)
			{
				throw new IndexOutOfRangeException(string.Format("ERROR: FixedPool.IndexOf(startIdx) failed. start idx = {0}, count = {1}", startIdx, Count));
			}
			return IndexOf(item, startIdx, Count - startIdx);
		}

		public int IndexOf(T item, int startIdx, int count)
		{
			for (int i = startIdx; i < count; i++)
			{
				if (object.ReferenceEquals(Pool[i], item))
				{
					return i;
				}
			}
			return -1;
		}

		public int LastIndexOf(T item)
		{
			return LastIndexOf(item, 0, Count);
		}

		public int LastIndexOf(T item, int startIdx)
		{
			if (startIdx > Count)
			{
				throw new IndexOutOfRangeException(string.Format("ERROR: FixedPool.LastIndexOf(startIdx) failed. start idx = {0}, count = {1}", startIdx, Count));
			}
			return LastIndexOf(item, startIdx, Count - startIdx);
		}

		public int LastIndexOf(T item, int startIdx, int count)
		{
			for (int num = startIdx + count - 1; num != startIdx - 1; num--)
			{
				if (object.ReferenceEquals(Pool[num], item))
				{
					return num;
				}
			}

			return -1;
		}

		public void Reverse()
		{
			Reverse(0, Count);
		}

		public void Reverse(int startIdx, int count)
		{
			int tail = startIdx + count - 1;
			int mid = startIdx + count / 2;
			int i = startIdx;
			int idx = 0;

			while (i < mid)
			{
				T t = Pool[i];
				Pool[i] = Pool[tail - idx];
				Pool[tail - idx] = t;
				i++;
				idx++;
			}
		}

		public void Sort(Comparison<T> comparison)
		{
			Sort(0, Count, comparison);
		}

		public void Sort(int startIdx, int count, Comparison<T> comparison)
		{
			FixedPool<T>.PoolComparer poolComparer;
			poolComparer.Comp = comparison;

			Array.Sort<T>(Pool, startIdx, count, poolComparer);
		}

		public T[] ToArray()
		{
			return Pool;
		}
	}
}
